/*
 * searchAndSort.cpp
 *
 *  Created on: Jul 15, 2012
 *      Author: xkq
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

vector<int> finding_intersections_of_2_sorted_arrays(vector<int> a, vector<int> b){
	vector<int> inter;
	int n1 = a.size();
	int n2 = b.size();
	int i=0,j=0;
	while(i<n1 && j<n2){
		if(a[i]<b[j]){
			i++;
		}else if(a[i]>b[j]){
			j++;
		}else{
			inter.push_back(a[i]);
			i++;
			j++;
		}
	}
	return inter;
}

set<vector<int> > finding_all_unique_triplets_sum_to_zero(vector<int> arr){
	sort(arr.begin(), arr.end());
	set<vector<int> > triplets;
	vector<int> triplet(3);
	int n=arr.size();
	for(int i=0; i<n-2; i++){
		int j=i+1, m=n-1;
		while(j<m){
			if(arr[i]+arr[j]+arr[m]<0){
				j++;
			} else if(arr[i]+arr[j]+arr[m]>0){
				m--;
			} else{
				triplet[0]=arr[i];
				triplet[1]=arr[j];
				triplet[2]=arr[m];
				triplets.insert(triplet);
				j++;
				m--;
			}
		}
	}
	return triplets;
}

/*no duplicates*/
int search_an_element_in_a_rotated_sorted_array(int a[], int n, int key){
	int l=0;
	int r=n-1;
	while(l<=r){
		int mid=l+(l+r)/2;
		if(a[mid] == key) return mid;
		if(a[l]<=a[mid]){
			if(a[l]<=key&&key<a[mid])
				r=mid-1;
			else
				l=mid+1;
		}else{
			if(a[mid]<key&&key<=a[r]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
	}
	return -1;
}

/* maximum window sliding
Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]*/

/* max heap*/
typedef pair<int, int> Pair;

void max_sliding_window(int a[], int n, int w, int b[]){
	priority_queue<Pair> q;
	for(int i=0; i<w; i++)
		q.push(Pair(a[i], i));
	for(int i=w; i<n; i++){
		Pair p=q.top();
		b[i-w]=p.first;
		while(p.second<=i-w){
			q.pop();
			p=q.top();
		}
		q.push(Pair(a[i], i));
	}
	b[n-w]=q.top().first;
}

/*double-ended queue*/
void max_sliding_window_double_ended_queue(int a[], int n, int w, int b[]){
	deque<int> q;
	for(int i=0; i<w; i++){
		while(!q.empty()&&a[i]>a[q.back()])
			q.pop_back();
		q.push_back(i);
	}
	for(int i=w; i<n; i++){
		b[i-w]=a[q.front()];
		while(!q.empty()&&a[i]>a[q.back()])
			q.pop_back();
		while(!q.empty()&&q.front()<=i-w)
			q.pop_front();
		q.push_back(i);
	}
	b[n-w] = a[q.front()];
}


/*Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.*/
int find_kth_smallest_element_in_union_of_2_sorted_array(int a[], int b[], int m, int n, int k){
	if()
}

set<vector<int> > sum_to_certain_value(int arr[], int n,int sum){
	//sort the array!!!
	vector<int> tmp(arr,arr+n);
	sort(tmp.begin(),tmp.end());
	for(int i=0;i<n;i++)
		arr[i] = tmp[i];
	vector<int> vec(2);
	set<vector<int> > pairs;

	int start = 0;
	int end = n-1;

	while(start<=end){
		if(arr[start]+arr[end]<sum)
			start++;
		else if(arr[start]+arr[end]>sum)
			end--;
		else{
			vec[0] = arr[start];
			vec[1] = arr[end];
			pairs.insert(vec);
		}

	}
	return pairs;
}

/*Reorder the array so that the odd numbers come before even numbers*/
void array_reorder(int arr[], int n){
	if(n==0) return;

	int start = 0;
	int end = n-1;

	while(start<=end){
		while(arr[start]%2!=0)
			start++;
		while(arr[end]%2==0)
			end++;
		int tmp = arr[start];
		arr[start] = arr[end];
		arr[end] = tmp;

		start++;
		end++;
	}
}

/* age sorting*/
void age_sort(int age[], int n) {
	if (age == NULL || n <= 0)
		return;
	const int ageIndex = 150;
	int hashTable[ageIndex + 1];

	for (int i = 0; i < ageIndex + 1; i++)
		hashTable[i] = 0;

	for (int i = 0; i < n; i++) {
		try {
			if (age[i] <= 0 || age[i] > ageIndex)
				throw "Age is out of range!";
			hashTable[age[i]]++;
		} catch (char const *str) {
			cout << str << endl;
		}
	}

	int k = 0;
	for (int i = 0; i < ageIndex + 1; i++) {
		for (int j = 0; j < hashTable[i]; j++) {
			age[k] = i;
			k++;
		}
	}
}

/*contiguous sequence with largest sum */
int contiguous_sequence_with_largest_sum(int arr[], int n){
	if(arr==NULL) return 0;

	int maxSum = 0;
	int currSum = 0;

	for(int i=0; i<n; i++){
		currSum+=arr[i];
		if(currSum>maxSum)
			maxSum=currSum;
		else if(currSum<=0)
			currSum = 0;
	}

	return maxSum;
}
